package 单链表;

import java.util.Stack;

public class 单链表 {
	public static void main(String[] args) {
		LinkNode node1 = new LinkNode(1,"小明");
		LinkNode node2 = new LinkNode(3,"小红");
		LinkNode node3 = new LinkNode(5,"小蓝");
		LinkNode node4 = new LinkNode(7,"小黑");
//		LinkNode node5 = new LinkNode(9,"小绿");
		
		LinkList list = new LinkList();
		
		//合并，两顺序链表合并

		LinkNode node6 = new LinkNode(4,"小");
		LinkNode node7 = new LinkNode(6,"小");
		
		LinkList list1 = new LinkList();
		LinkList list2 = new LinkList();
		//不能使用上面声明的node1、node2，可能是因为链表引用了node会改变它的值
		list1.addByOrder(new LinkNode(1,"小明"));
		list1.addByOrder(new LinkNode(3,"小明"));
		list1.addByOrder(new LinkNode(5,"小明"));
		list1.addByOrder(new LinkNode(7,"小明"));
		
		list2.addByOrder(node6);
		list2.addByOrder(node7);
		
		
		//按no顺序创建，添加
//		list.addByOrder(node1);
//		list.addByOrder(node4);
//		list.addByOrder(node3);
//		list.addByOrder(node2);
		
		//头插法创建，添加
		list.addAtHead(node1);
		list.addAtHead(node2);
		list.addAtHead(node3);
		list.addAtHead(node4);
		list.showList();
		
		System.out.println("------------合并--------------");
		list1.merge(list1, list2);
		
		System.out.println("------------逆序打印--------------");
		list.reversePrint();
		
		System.out.println("------------反转--------------");
		list.reverseList();
		
		list.showList();
		System.out.println("------------更新-------------");
		list.update(new LinkNode(3, "小兰"));
		list.showList();
		System.out.println("------------删除--------------");
		list.delete(1);
		list.delete(3);
		list.showList();
		
		System.out.println("--------------------------");
		//辅助指针是和原来的对象同一地址："=" 引用，所以辅助指针 p 可以代表 L
		LinkList l = list;
		l.delete(5);
		list.showList();
		
	}
}

//链表
class LinkList{
	//头结点
	private LinkNode L;
	
	//初始化链表
	public LinkList() {
		L = new LinkNode();
		L.next = null;
//		this.L = null;
	}
	
	public LinkNode getHead() {
		return L;
	}
	
	//头插法，创建添加
	public void addAtHead(LinkNode newNode) {
		//在链表头部插入，头结点next是空的，所以第一个插入的节点在最后，next肯定也是空的
		//如果不是第一个插入的，next域就是插入之前排第一的节点，链表第一个结点用L.next表示
		
		//表示将新结点放到链表第一个结点之前
		newNode.next = L.next;//L.next表示链表第一个结点
		
		//将头结点与新结点连起来
		L.next = newNode;
	}
	
	
	//添加，按no顺序，保证数据无重复前提
	public void addByOrder(LinkNode newNode) {
	
		//头结点不能动，生成辅助接点 p/temp,指向头结点
		LinkNode p = L;//指向头结点，L.next是指向首元结点，看情况定；
		//System.out.println(p == L);
		//是否找到插入位置
		boolean flag = false;
		
		while(true) {
		//while(p.next != null) { //合并写法
			if(p.next == null) {
				//到最后了,就加到最后
				break;
			}
			if(p.next.no > newNode.no) {
				//找到位置
				break;
			}else if(p.next.no == newNode.no) {
				//找到相同结点，链表不允许重复情况下就跳出
				flag = true;
				break;
			}
			//都没有,继续下一个
			p = p.next;
		}
		
		//找完了
		if(flag) {
			System.out.println("已存在！");
		}else {
			//插入，先连接 后面一个结点 和 新结点 ，然后断开 前一个和后一个结点(前一个指向新的)
			newNode.next = p.next;
			p.next = newNode;
			
 		}
		
	}
	
	
	//链表的反转
	public void reverseList() {
		//空链表或链表长度为 1 
		if(L.next == null || L.next.next == null) {
			return;
		}
		//1.先使用一个新结点保存部分移动之后的结点，暂存
		//2.p 指针指向原始链表，next 指针指向p 后面的结点
		
		//反转链表，用来暂存数据
		LinkList reverseList = new LinkList();
		//原始链表指针,目前指向第一个结点
		LinkNode p = L.next;
		//记录指针
		LinkNode next = null;
		
		while(p != null) {
			//1.记录p 后面的结点，目前指向第二个结点
			next = p.next;
			//2.将反转链表的第一个结点位置给p ，因为reverseList.L.next是空的，反转之后
			//最后一个节点next 也是空的
			p.next = reverseList.L.next;
			//3.将p 连到反转列表上
			reverseList.L.next = p;
			//3.将原始链表p 向后移，L 断了没关系，next保存了后面链表数据，还能继续循环
			p = next;
		}
		//如果都反转完了，将reverseList链表第一个结点给原始链表，后面也带过去了
		//如果有返回，也可以直接返回新的反转链表
		L.next = reverseList.L.next;
		
	}
	
	//逆序打印
	public void reversePrint() {
		if(L.next == null) {
			System.out.println("链表空！");
		}
		LinkNode p = L.next;
		Stack<LinkNode> stack = new Stack<LinkNode>();
		
		while(p != null) {
			//入栈
			stack.push(p);
			p = p.next;
		}
		
		while(stack.size()>0) {
			//出栈
			System.out.println(stack.pop());
		}
	}
	
	
	//更新
	public void update(LinkNode newNode) {
		
		LinkNode p = L.next;
		
		if(p == null) {
			System.out.println("链表空！");
			return;
		}
		
		while(p != null) {
			if(p.no == newNode.no) {
				p.name = newNode.name;
				//如果列表无重复，此时返回即可
				return;
			}
			p = p.next;
		}
		
		System.out.println("未找到，更新失败！");
	}
	
	//删除
	public void delete(Integer no) {

		LinkNode p = L;
		
		if(p.next == null) {
			System.out.println("链表空！");
			return;
		}
		
		while(p.next != null) {
			if(p.next.no == no) {
				//找到被删结点前一个，只能找前一个，不然连不上
				//直接跳过中间结点，连接下一个结点
				p.next = p.next.next;
				//如果链表不重复，直接返回
				return;
			}
			p = p.next;//*-*-*-*-*-*-*-*-*-*-*-*-一定不要忘*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
		}
		System.err.println("未找到，删除失败！");
	}
	
	//合并
	public void merge(LinkList list1, LinkList list2) {
		
		if(list1 == null || list2 == null) {
			System.out.println("空!");
		}
		
		//新链表
		LinkList newList = new LinkList();
		//新链表的尾
		LinkNode tail = newList.L;
		LinkNode p1 = list1.L.next;
		LinkNode p2 = list2.L.next;
		//遍历
		while(p1 != null && p2 != null) {
			if(p1.no <= p2.no) {
				//找到小的
				tail.next = p1;
				//移动被选出的那个和变动的新链表的尾
				p1 = p1.next;
				tail = tail.next;
			}else {
				tail.next = p2;
				p2 = p2.next;
				tail = tail.next;
			}
		}
		
		while(p1 != null) {
			tail.next = p1;
			p1 = p1.next;
			tail = tail.next;
		}
		while(p2 != null) {
			tail.next = p2;
			p2 = p2.next;
			tail = tail.next;
		}
		newList.showList();
	}
	
	//遍历
	public void showList() {
		
		LinkNode p = L.next;
		
		if(p == null) {
			System.out.println("链表空！");
			return;
		}
		
		
		//注意不是p.next == null,因为这样最后一个不会进去
		while(p != null) {
			System.out.println(p);
			p = p.next;
		}
	}
}

//结点
class LinkNode{
	//数据域，可以有多个字段
	public Integer no;
	public String name;
	
	//指针域，与结点同类型
	public LinkNode next;
	
	public LinkNode() {
	}

	//没有  LinkNode next 字段
	public LinkNode(Integer no, String name) {
		super();
		this.no = no;
		this.name = name;
	}

	//toString方法不要写next ，不然每一个next都会显示整个链表
	@Override
	public String toString() {
		return "LinkNode [no=" + no + ", name=" + name + "]";
	}
	
}